There are many conventional multiplication circuits that perform squaring. Typically, these circuits include an array of partial product bit generators, each bit generator providing a bit of a partial product by comparing the appropriate bits of the multiplicand and multiplier.
Each partial product bit of a common weight is provided to a column adder corresponding to the common weight. The complexity of the adder tree for a given column depends on the number of bits that are added in that column. Typically, the more complex an adder tree, the larger and slower the column adder. Therefore, a circuit and method for reducing the number of bits corresponding to a given column adder are desired.
This reduction is particularly important for the column with the most partial product bits. In many conventional circuits, each column is standardized with a common tree structure that is designed to meet the requirements of the column with the most bits. In these cases, a reduction in the maximum bits per column reduces the complexity of the adder tree structure for every column. Therefore, a circuit and method for reducing the maximum bits added per column is desired.
In accordance with the present invention, a circuit reduces the number of partial product bits in a column. The circuit includes a partial product bit generator, corresponding to the column, that generates a partial product bit of weight 22k (k is an integer). This partial product bit has a 1 value only if an input bit of weight 2(kxe2x88x92i) has a 0 value while another input bit of weight 2k has a 1 value. The circuit includes another partial product bit generator that receives the same two input bits. The second partial product bit generator provides a partial product bit of weight 22k+i, wherein the second partial product bit has a 1 value only if both of the input bits have a 1 value.
In accordance with the present invention, a method is provided in which a partial product bit of weight 22k is generated having a 1 value only if the input bit of weight 2(kxe2x88x921) has a 0 value while the input bit of weight 2k has a 1 value. A partial product bit of weight 22k+1 is generated having a 1 value only if both of the input bits have a 1 value. Another method includes providing the partial product bit generators described above.
The present invention and its advantages and features will be more fully understood in light of the following detailed description and the claims.